package binaryTree_practise;

public class BinaryTree {
    //目前在我的认知中 创建二叉树需要明确的前序遍历序列
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public int strIndex;

    //创建二叉树
    public TreeNode createBinaryTree(String str) {
        //保证所给序列无错误
        if(str == null || str.charAt(strIndex)=='#') {
            strIndex++;
            return null;
        }
        TreeNode root = new TreeNode(str.charAt(strIndex));
        strIndex++;
        root.left = createBinaryTree(str);
        root.right = createBinaryTree(str);
        return root;
    }

    //递归前序遍历
    public void preorderTraversal(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    //根据中序遍历序列+后序遍历序列 创建二叉树
    /*public int i;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.i = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] inorder, int[] postorder, int pIndex, int head, int last) {
        if(last<head) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[i]);

        pIndex = findKeyIndex(inorder,postorder[i],head,last);

        i--;

        root.left = buildTreeChild(inorder,postorder,pIndex,head,pIndex-1);
        root.right = buildTreeChild(inorder,postorder,pIndex,pIndex+1,last);

        return root;
    }
    public int findKeyIndex(int[] inorder, int key, int head, int last) {
        for(int j = head; j <= last; j++) {
            if(inorder[j]==key) {
                return j;
            }
        }
        return -1;
    }*/


    //根据前序遍历序列+中序遍历序列 创建二叉树
    /*
    class Solution {
    public int i;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //根据前序遍历 和 中序遍历 构造一棵二叉树
        //由于前序遍历是根-》左-》右 中序遍历是左-》根-》右
        //故当得到前序中某个元素时，再去中序遍历寻找，即可得左、右树
        //由于本函数仅存在两个参数 递归无望 故需要另创建方法

        return buildTreeChild(preorder,inorder,0,0,inorder.length-1);
    }
    //为了保证前序可以按顺序正常递归下去，故应将其设为成员变量
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int pIndex, int head, int last) {
        //参数链表：前序遍历序列数组 中序遍历序列数组 根节点在中序遍历序列数组中对应的下标 中序头下标 中序尾下标
        if(last<head) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[i]);

        pIndex = findPIndex(inorder,preorder[i],head,last);

        i++;

        root.left = buildTreeChild(preorder,inorder,pIndex,head,pIndex-1);

        root.right = buildTreeChild(preorder,inorder,pIndex,pIndex+1,last);

        return root;
    }

    public int findPIndex(int[] inorder, int key, int head, int last) {
        for(int j = head; j <= last; j++) {
            if(inorder[j]==key) {
                return j;
            }
        }
        //由于以保证序列正确并且无重复元素 故该语句不会不执行
        return -1;
    }
}
    */
}

